\onlyLong{
\vspace{-0.5cm}
\subsection{Lower Bounds} \label{sec:lb}
\vspace{-0.1cm}
\onlyLong{In this section}\onlyShort{In the full paper} we show lower bounds on the number of rounds for computing a minimal connected dominating set (\mcds).
First, we show that $\tilde{\Omega}(D + \sqrt{n})$ rounds are necessary in the worst case for solving \mcds in the CONGEST model showing a reduction to the spanning connected subgraph problem (\scs).  

We then consider the LOCAL model where nodes can send messages of unbounded size.
Here we present a lower bound
of $\Omega(D)$ rounds for computing a minimal connected dominating set (\mcds).
While it is easy to see that this lower bound holds on a cycle of $n$ nodes, we
show that $\Omega(D)$ is a \emph{universal} bound in the sense that, for any given diameter $D=D(n)$ as a function of $n$, we can construct a graph where the algorithm takes $\Omega(D)$ time.
As a byproduct of our proof, we obtain the same lower bound for spanning tree computation and maximal clique.
%Together with our algorithms from \Cref{sec:applications}, this shows a clear separation between computing \rmds and the (strictly harder) problem of computing a \mcds.
}
\onlyLong{
\begin{theorem} \label{thm:CONGEST-lb}
There exists an $\epsilon > 0$ and a graph $G$ of $n$ nodes and diameter $D$, such that any $\epsilon$-error \mcds algorithm $R$ takes $\tilde{\Omega}(D + \sqrt{n})$ rounds in the CONGEST model.
\end{theorem}
%\onlyShort{\begin{proof}[Proof Sketch:]}
\begin{proof}
We will show the lower bound via reduction from the spanning connected subgraph (\scs) problem, for which an $\tilde{\Omega}(D + \sqrt{n})$ lower bound is already known (cf.\ \cite{STOC11}).
Consider an instance of the \scs problem: we are given a set of edges defining a subgraph $H$ of graph $G$ and every node must output ``yes'' if $H$ spans $G$ and is connected; otherwise at least one node must output ``no''.

Suppose that we are given the \mcds algorithm $R$ as stated in the theorem.
We will first show that, as long as graph $G$ has $O(n)$ edges, we can instantiate $R$ to yield a solution for \scs without significant overhead.
Since the lower bound graph for the \scs problem in \cite{STOC11} has $O(n)$ edges, this will yield the result.
}
\onlyLong{
For an instance of \scs given by $G$ and $H \subseteq G$, we will construct a graph $G' = G'(G,H)$ of $\Theta(|V(G)|)$ vertices and $\Theta(|E(G)|)$ edges:
We initialize $V(G')$ to $V(G)$ and subdivide each edge $(u,v) \in E(G)$ by adding a \emph{subdividing vertex} $b_{u,v}$ to $V(G')$ and
edges $(u,b_{u,v})$, $(b_{u,v},v)$ to $E(G')$.
Let $B[H]$ be the set of all vertices that subdivide an edge in $H$ and let $B[G\setminus H]$ be the set of vertices subdividing other edges in $E(G) \setminus E(H)$.
Then, for every vertex $u \in V(G) \cup B[H]$ we add an \emph{outer vertex} $g_u$ to $V(G')$ and attach it to $u \in V(G')$ by adding the edge $(g_u,u)$ to $E(G')$.
In other words, we attach outer vertices to all nodes that were part of the original graph $G$ and to all nodes that subdivide an edge in $H$.

\begin{lemma} \label{lem:scs}
If $M$ is an minimal connected dominating set of $G'$, then the following holds:
$\forall u \in M\colon u \notin B[G\setminus H]$ if and only if $H$ is a spanning connected subgraph of $G$'
%Graph $H$ is a spanning connected subgraph of $G$ if and only if the MCDS of $G'$ does not contain any nodes that subdivide an edge not in $H$.
%We can claim that the H is spanning connected iff the MCDS that we get contains 
%NO blue nodes in the middle of edges not in H. 
\end{lemma}
\onlyLong{
\begin{proof}
First, observe that to dominate an outer vertex $g_u$, it is necessary that either $g_u \in M$ or its (only) neighbor $v$ is in $M$.
In the former case, it follows that $v$ must also be in $M$ to satisfy connectivity.
But then we could remove $g_u$ from $M$ and still guarantee domination; thus it follows that no outer vertex is in $M$ and, every neighbor of an outer vertex is in $M$.
In particular, this means that all vertices of $G$ and all vertices that subdivide edges of $H$ must be in $M$ (since for each of these we added an outer vertex).
Finally, we observe that $H$ is not a connected subgraph if and only if $M$ needs to contain vertices that subdivide edges \emph{not} in $H$.
This completes the proof of \Cref{lem:scs}.
\end{proof}
}
Armed with \Cref{lem:scs}, we can simply invoke algorithm $R$ to test whether $H$ is a spanning connected subgraph of $G$.
Assuming that $|E(G)| \in O(n)$, it follows that asymptotically $G'$ and $G$ have the same number of vertices and edges and thus it is straightforward to simulate the run of the MCDS algorithm $R$ on the (virtual) graph $G'$ on top of the actual network $G$.
From \cite{STOC11} we know that there exists a graph of $n$ nodes and $O(n)$ edges where \scs takes time $\Omega(D + \sqrt{n})$.
This completes the proof of \Cref{thm:CONGEST-lb}.
\end{proof}
}
\onlyLong{
\begin{theorem}[Universal Lower Bound] \label{thm:MCDS-ST-lowerbound}
Let $R$ be an algorithm that computes a Spanning Tree  (resp.\ maximal clique and \mcds) in the LOCAL model with probability at least $15/16+\eps$, for any constant $\eps>0$.
Then, for every sufficiently large $n$ and every function $D(n)$ with $2 \le D(n) < n/4$, there exists a graph $G$ of $n' \in \Theta(n)$ nodes and diameter $D' \in \Theta(D(n))$ where $R$ takes $\Omega(D)$ rounds with constant probability.
%This is true even if all nodes know $n'$ and $D'$, and wake up simultaneously.
%This is true even if the algorithm is aware of the entire topology of $G$.
%If nodes are equipped with unique ids, then $\beta < 1/16 - 1/n$.
\end{theorem}

\begin{proof}
For a given $n$ and a function $D(n)$, we construct the following lower bound graph $G$ of $\Theta(n)$ nodes and diameter $\Theta(D(n))$.
Let $d \ge 1$ be the largest integer such that $n = 4d D(n) + \ell$, for $0 \le \ell < 4D$; we will construct a graph $G$ of $n' = n - \ell \in \Theta(n)$ vertices and diameter $D' = \lfloor (n - \ell)/8d \rfloor \in \Theta(D)$.
Let $u_0,\dots,u_{n'-1}$ be the vertices of $G$.
We will consider the set of \emph{bridge vertices} defined as $\{u_i \in V(G) \mid \exists k\ge 0\colon i = k d < n'\}$ to describe the edges of $G$; vertices not in this set are the \emph{non-bridge vertices} of $G$.
That is, for every bridge vertex $u_i$, we add the arc edges $(u_i,u_{i+1}),(u_i,u_{i-1}),\dots,(u_i,u_{i+d}),(u_i,u_{i-d})$ (indices are modulo $n'$).
See \Cref{fig:lbGraph} for a concrete instance of this graph.
\input{lbgraph}

We first observe that solving maximal clique in this graph provides a leader node by simply running the $O(1)$ time leader election algorithm of \cite{KPPRT-LE-ICDCN13} on the clique, thus showing that maximal clique takes $\Omega(D)$ time. 

We now describe how to solve the leader election problem on $G$ given an \mcds-algorithm or an \st-algorithm. 
Let $b_0,\dots,b_{n'/4d-1}$ be an ordering of the bridge vertices according to their adjacencies in $G$.
As there are no edges between non-bridge vertices, any \mcds $M$ must contain all except possibly $1$ bridge vertex to guarantee connectivity.
Moreover, the fact that every bridge vertex $b_i$ dominates $b_{i-1}$ and $b_{i+1}$ (modulo $n'/4d$) implies that $M$ must omit a bridge vertex to be minimal.


\begin{observation} \label{obs:mcds}
If $M$ is an \mcds of $G$, then there is exactly one bridge vertex $b_i \in G$ such that $b_i \notin M$.
\end{observation}

We call the subgraph that consists of a bridge vertex $b_i$ and its adjacent vertices a \emph{bridge cluster}.
Analogously to \Cref{obs:mcds}, we have the following:

\begin{observation} \label{obs:st}
Let $B$ be a partitioning of $G$ into edge-disjoint bridge clusters and let $S$ be a spanning tree of $G$.
Then, there is exactly one bridge cluster $b \in B$ such that the subgraph $b \cap S$ is disconnected.
\end{observation}

Suppose that $R$ is an algorithm that solves \st (the argument is analogous for \mcds) with probability $p$ in time $T$.
We first run $R$ to obtain a spanning tree of $G$ and then instruct every bridge vertex to check whether its cluster is connected.
By construction, every vertex locally knows if it is a bridge vertex since non-bridge vertices have exactly $2$ edges while bridge vertices have degree $>2$.
% that checking for connectivity can be done in one round.
By \Cref{obs:st}, exactly $2$ bridge vertices $b_i$ and $b_{i+1}$ will determine that their (overlapping) clusters are disconnected.
The nodes $b_i$ and $b_{i+1}$ determine which of them has the greater id; this node then elects itself as the leader, while all other nodes enter the non-elected state.
Thus there is an algorithm that elects a leader in $O(T)$ rounds with probability $p$.

It was shown in Theorem~3.13 of \cite{KPPRT13:PODC} that  there is a class of graphs $G_n$ with diameter $D(n)$ such that leader election takes $\Omega(D(n))$ rounds with constant probability.
The proof of this result relies on the fact that the vertices of $G_n$ can be partitioned into $4$ disjoint but symmetric sets $C_1,\dots,C_4$ such that the distance between $C_1$ and $C_3$ (resp.\ $C_2$ and $C_4$) is $\Omega(D)$.
It is straightforward to check that these properties also hold true in our graph class $G$.
In particular, all bridge vertices observe the same round $r$-neighborhood of $G$, for all $r \ge 1$.
Thus the proof of Theorem~3.13 in \cite{KPPRT13:PODC} can be adapted to our graph $G$.
(We defer the details of this adaptation to the full version of the paper.)
Together with the above reduction from leader election, 
this implies the sought time bound of $\Omega(D)$ rounds (with constant probability) for computing a minimal connected dominating set and finding a spanning tree on $G$.
\end{proof}
}
%
%\peter{TODO: Corollaries of \st lower bound!}
%
\endinput
